The present invention relates to an information storage system and a data replication method thereof, and particularly, relates to data replication in an information storage system including a plurality of information storage nodes.
In a computing system, information required by a system is often stored in a database. A relational database is one of the most widely known databases. A relational database offers excellent functions such as data coupling and consistency of data in transactions. On the one hand, the relational database does not necessarily have high scalability.
With advancement of the distribution technology over Internet such as the cloud technology, a system is required that can increase the number of servers on demand, while enabling a multitude of servers to perform high-speed distributed processing. As a technology that can meet such a need, a key value store is attracting attention. A key value store stores a pair of a key and a value. A system specifies a key of a target value to acquire the value. By changing, depending on a key value, a destination server (node) in which a key is saved depending on a key value, the key value store can distribute data and save them in a plurality of servers. Thus, the key value store can easily construct a scale-out system which processes a large amount of data. The consistent hashing is known as a technique to determine a responsible node depending on a key value (See Non-Patent Literature 1, for example.)
In addition, Non-Patent Literature 2 discloses a technology to achieve high availability in a key value store. Specifically, the literature discloses replications of data by a plurality of hosts to achieve high availability and durability. Each data item is replicated and stored in N units of hosts which are set with respect to each instance. A coordinator node is assigned to each key. The coordinator node is responsible for replication of a data item which is assigned thereto. In addition to storing of each of the keys for which it is responsible in its own memory, the coordinator node replicates the keys to adjacent N−1 units of nodes in a clockwise direction in a ring arrangement.
Non-Patent Literature 2 discloses a method for adding a new node X and a method for removing a node from a system. By adding the new node X, a specific key range is assigned to X. Some existing nodes, which have retained keys newly assigned to the node X, no longer need to have those keys. The existing nodes transfer to the node X the keys which they no longer need to keep. Similarly, when a node is removed from a system, keys are relocated in reverse steps to the node addition.
In Non-Patent Literature 3, in order to improve data availability, one key is mapped to k points in a coordinate space by means of k different hash functions so as to replicate and store one key value pair in k different nodes in a system.
Non-Patent Literature 1: Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web, D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin and R. Panigrahy, In: Proc. 29th Ann. ACM Symp. On Theory of Computing, 1997, pp. 654-663
Non-Patent Literature 2: Dynamo: amazon's highly available key value store, G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall, W. Vogels : In: SOSP. Pp. 205-220 (2007)
Non-Patent Literature 3: A Scalable Content-Addressable Network, Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, SIGCOMM'01, Aug. 27-31, 2001, San Diego, Calif., USA